package com.my.collection.graph.v5;

import com.my.collection.graph.v1.ElementExistException;
import com.my.collection.graph.v1.ElementNotFoundException;

import java.util.*;

/**
 * Created by ZhongGang
 * at 2018/10/25 9:28
 */
public class Graph<V> {
    private Map<V, Set<V>> table = new HashMap<>();

    public void addVertex(V v) {
        if (this.table.containsKey(v)) {
            throw new ElementExistException();
        }

        this.table.put(v, new HashSet<>());
    }

    public void addEdge(V from, V to) {
        if (!this.table.containsKey(from) || !this.table.containsKey(to)) {
            throw new ElementNotFoundException();
        }

        this.table.get(from).add(to);
    }

    /**
     * 图的反向图
     *
     * @return
     */
    public Graph<V> reverse() {
        Graph<V> reverseGraph = new Graph<>();
        //添加顶点
        for (V v : table.keySet()) {
            reverseGraph.addVertex(v);
        }

        //添加边
        for (Map.Entry<V, Set<V>> entry : table.entrySet()) {
            V vertex = entry.getKey();
            Set<V> edges = entry.getValue();
            for (V edge : edges) {
                reverseGraph.table.get(edge).add(vertex);
            }
        }

        return reverseGraph;
    }

    /**
     * 拓扑排序
     *
     * @return
     */
    public List<V> topology() {
        throw new UnsupportedOperationException();
    }

    /**
     * 计算有向图连通分量
     *
     * @return
     */
    public int kosaraju() {
        throw new UnsupportedOperationException();
    }

    /**
     * 计算有向图连通分量
     *
     * @return
     */
    public int tarjan() {
        throw new UnsupportedOperationException();
    }
}
